package problems;

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

import lib.Permutations;

public class Euler038 extends AbstractEuler {

	@Override
	public Number calculate() {
		List<String> digits = Arrays.asList("9", "8", "7", "6", "5", "4", "3", "2", "1");
		
		Iterator<List<String>> p = new Permutations<String>(digits, digits.size());
		while (p.hasNext()) {
			List<String> nextBiggest = p.next();
			if (isConcatenatedProduct(nextBiggest)) {
				StringBuffer strbuf = new StringBuffer();
				for (String digit : nextBiggest) {
					strbuf.append(digit);
				}
				return Integer.valueOf(strbuf.toString());
			}
		}

		fail();
		return null;
	}
	
	private boolean isConcatenatedProduct(List<String> digits) {
		next:
		for (int startSize = 1; startSize < 8; startSize++) {
			StringBuffer strbuf = new StringBuffer();
			for (String digit : digits.subList(0, startSize)) {
				strbuf.append(digit);
			}
			int firstNumber = Integer.valueOf(strbuf.toString());
			
			for (int multiplier = 1, lastPosition = 0; lastPosition <= 8; multiplier++) { //given example was 9 and (1,2,3,4,5), so multiplier <= 5
				int targetNumber = firstNumber * multiplier;
				strbuf = new StringBuffer().append(targetNumber);
				if (lastPosition + strbuf.length() > digits.size()) continue next;
				for (int i = 0; i < strbuf.length(); i++) {
					if (strbuf.charAt(i) != digits.get(lastPosition + i).charAt(0)) continue next;
					if (lastPosition + i == digits.size() - 1) {
//						System.out.println(firstNumber + " * 1 .. " + multiplier);
						return true;
					}
				}
				
				lastPosition += strbuf.length();
			}
		}
		
		return false;
	}
	
	public void testConcatenation() {
		assertTrue(isConcatenatedProduct(Arrays.asList("1", "9", "2", "3", "8", "4", "5", "7", "6")));
	}

	@Override
	protected Number getCorrectAnswer() {
		return 932718654;
	}

}
